#include <iostream>
#include <vector>
#include <cmath>
#include <limits>
#include <algorithm>
#include <memory>
#include <thread>
#include <mutex>
#include <atomic>
#include <unordered_set>
#include <functional>
#include <iterator>
#include <queue> // 新增：用于层次遍历

using namespace std;

// 飞行线结构体（保持不变）
struct FlightLine
{
    int id;
    double x1, y1, x2, y2;

    pair<pair<double, double>, pair<double, double>> getBoundingBox() const
    {
        return {{min(x1, x2), min(y1, y2)}, {max(x1, x2), max(y1, y2)}};
    }
};

// 查询点结构体（保持不变）
struct QueryPoint
{
    double x, y;
};

// 计算点到线段的平方距离
double pointToLineSquaredDistance(double px, double py, const FlightLine &line)
{
    double x1 = line.x1, y1 = line.y1;
    double x2 = line.x2, y2 = line.y2;

    double dx = x2 - x1;
    double dy = y2 - y1;
    double lineLengthSq = dx * dx + dy * dy;

    if (lineLengthSq == 0)
    {
        return (px - x1) * (px - x1) + (py - y1) * (py - y1);
    }

    double t = ((px - x1) * dx + (py - y1) * dy) / lineLengthSq;
    t = max(0.0, min(1.0, t));

    double projectionX = x1 + t * dx;
    double projectionY = y1 + t * dy;

    return (px - projectionX) * (px - projectionX) + (py - projectionY) * (py - projectionY);
}

// 计算点到包围盒的最小平方距离
double pointToBBoxMinSquaredDistance(double px, double py, const pair<pair<double, double>, pair<double, double>> &bbox)
{
    double dx = max({bbox.first.first - px, 0.0, px - bbox.second.first});
    double dy = max({bbox.first.second - py, 0.0, py - bbox.second.second});
    return dx * dx + dy * dy;
}

// 前向声明
pair<int, double> findSplit(const vector<FlightLine> &lines, int axis);

/*不足1：当输入的lines为空时直接返回nullptr，但未对调用方进行提示或抛出异常。
影响：若调用方传入空数据集，可能导致后续操作（如查询）出现空指针解引用的风险。
 */

/*不足 2：插入 / 删除后树的平衡性未维护
代码现状：插入和删除操作采用简单的递归方式，未使用平衡策略（如旋转、重构子树），可能导致树退化为链表，查询效率下降至 O (n)。
影响：频繁动态更新后，KD 树的查询性能会显著降低。*/

// KD树节点结构体（核心修改部分）
struct KDNode : public std::enable_shared_from_this<KDNode>
{ // 继承enable_shared_from_this
    int id;
    FlightLine line;
    shared_ptr<KDNode> left;
    shared_ptr<KDNode> right;
    weak_ptr<KDNode> parent; // 使用weak_ptr避免循环引用
    int axis;
    double splitValue;
    pair<pair<double, double>, pair<double, double>> bbox;

    KDNode(const FlightLine &line, int axis, double split)
        : id(line.id), line(line), left(nullptr), right(nullptr),
          axis(axis), splitValue(split), bbox(line.getBoundingBox()) {}

    // 更新包围盒（包含子节点）
    void updateBoundingBox()
    {
        bbox = line.getBoundingBox();
        if (left)
        {
            bbox.first.first = min(bbox.first.first, left->bbox.first.first);
            bbox.first.second = min(bbox.first.second, left->bbox.first.second);
            bbox.second.first = max(bbox.second.first, left->bbox.second.first);
            bbox.second.second = max(bbox.second.second, left->bbox.second.second);
        }
        if (right)
        {
            bbox.first.first = min(bbox.first.first, right->bbox.first.first);
            bbox.first.second = min(bbox.first.second, right->bbox.first.second);
            bbox.second.first = max(bbox.second.first, right->bbox.second.first);
            bbox.second.second = max(bbox.second.second, right->bbox.second.second);
        }
    }

    // 插入新线段（局部更新）
    void insert(const FlightLine &newLine, int depth = 0)
    {
        int axis = depth % 2;
        double lineMid = axis == 0 ? (newLine.x1 + newLine.x2) / 2 : (newLine.y1 + newLine.y2) / 2;
        bool goLeft = lineMid < splitValue || (lineMid == splitValue && newLine.id < id);

        if (goLeft)
        {
            if (!left)
            {
                left = make_shared<KDNode>(newLine, axis, lineMid);
                left->parent = shared_from_this();
            }
            else
            {
                left->insert(newLine, depth + 1);
            }
        }
        else
        {
            if (!right)
            {
                right = make_shared<KDNode>(newLine, axis, lineMid);
                right->parent = shared_from_this();
            }
            else
            {
                right->insert(newLine, depth + 1);
            }
        }
        updateBoundingBox(); // 自底向上更新包围盒
    }

    // 删除线段（路径重构）
    bool remove(int targetId, int depth = 0)
    {
        if (id == targetId)
        {
            // 处理当前节点删除
            if (left && right)
            {                                                 // 双分支节点
                auto replaceNode = right->findLeftmostLeaf(); // 右子树最左叶子
                line = replaceNode->line;
                splitValue = (depth % 2 == 0) ? (line.x1 + line.x2) / 2 : (line.y1 + line.y2) / 2;
                replaceNode->parent.lock()->left = nullptr; // 删除替换节点
            }
            else
            { // 单分支或叶子节点
                auto p = parent.lock();
                if (p)
                {
                    if (p->left == shared_from_this())
                        p->left = left ? left : right;
                    else
                        p->right = left ? left : right;
                    if (p->left)
                        p->left->parent = p;
                    if (p->right)
                        p->right->parent = p;
                }
                return true; // 标记删除成功
            }
        }

        bool removed = false;
        int axis = depth % 2;
        bool goLeft = (axis == 0 ? line.x1 : line.y1) < splitValue;

        if (goLeft && left)
            removed = left->remove(targetId, depth + 1);
        if (!removed && right)
            removed = right->remove(targetId, depth + 1);

        if (removed)
            updateBoundingBox(); // 更新父节点包围盒
        return removed;
    }

    // 查找最左叶子节点
    shared_ptr<KDNode> findLeftmostLeaf()
    {
        auto curr = shared_from_this();
        while (curr->left)
            curr = curr->left;
        return curr;
    }
};

/*不足 1：重复计算中点坐标
代码现状：插入操作中，每次比较新线段的中点与当前节点的分割值时，重复计算newMid = (x1+x2)/2或(y1+y2)/2。
影响：对于大量插入操作，会产生不必要的计算开销。*/

// 寻找分割点（保持不变）
pair<int, double> findSplit(const vector<FlightLine> &lines, int axis)
{
    if (lines.empty())
        return {0, 0.0};
    vector<double> values;
    for (const auto &line : lines)
    {
        values.push_back(axis == 0 ? (line.x1 + line.x2) / 2 : (line.y1 + line.y2) / 2);
    }
    sort(values.begin(), values.end());
    int mid = values.size() / 2;
    return {mid, values[mid]};
}

// 并行构建KD树（添加父指针）
shared_ptr<KDNode> buildKDTreeParallel(vector<FlightLine> &flightLines, int depth = 0, bool parallel = true)
{
    if (flightLines.empty())
        return nullptr;
    int axis = depth % 2;
    auto [mid, splitVal] = findSplit(flightLines, axis);
    auto node = make_shared<KDNode>(flightLines[mid], axis, splitVal);

    vector<FlightLine> leftLines(flightLines.begin(), flightLines.begin() + mid);
    vector<FlightLine> rightLines(flightLines.begin() + mid + 1, flightLines.end());

    if (!leftLines.empty())
    {
        node->left = buildKDTreeParallel(leftLines, depth + 1, false);
        if (node->left)
            node->left->parent = node;
    }
    if (!rightLines.empty())
    {
        node->right = buildKDTreeParallel(rightLines, depth + 1, false);
        if (node->right)
            node->right->parent = node;
    }
    node->updateBoundingBox();
    return node;
}

/*不足 2：搜索时未利用提前终止条件
代码现状：nearestSearch函数中，即使当前节点的线段距离已大于当前最小距离，仍可能继续遍历子树（除非包围盒距离剪枝）。
影响：对于某些情况，可能遍历无效节点，增加计算量。*/
// 搜索函数（保持不变）
void searchKDTree(shared_ptr<KDNode> node, const QueryPoint &query,
                  double &minSqDist, int &nearestId)
{
    if (!node)
        return;
    double bboxDist = pointToBBoxMinSquaredDistance(query.x, query.y, node->bbox);
    if (bboxDist > minSqDist)
        return;

    double lineDist = pointToLineSquaredDistance(query.x, query.y, node->line);
    if (lineDist < minSqDist || (lineDist == minSqDist && node->id < nearestId))
    {
        minSqDist = lineDist;
        nearestId = node->id;
    }

    double qVal = node->axis == 0 ? query.x : query.y;
    bool goLeft = qVal < node->splitValue;
    if (goLeft)
    {
        searchKDTree(node->left, query, minSqDist, nearestId);
        if ((qVal - sqrt(minSqDist)) <= node->splitValue)
            searchKDTree(node->right, query, minSqDist, nearestId);
    }
    else
    {
        searchKDTree(node->right, query, minSqDist, nearestId);
        if ((qVal + sqrt(minSqDist)) >= node->splitValue)
            searchKDTree(node->left, query, minSqDist, nearestId);
    }
}

/*不足 1：线程间负载分配不够高效
代码现状：并行查询使用轮询分配索引，但当查询点分布不均匀时，可能导致某些线程处理的查询点计算量更大（如靠近树中心的点需要遍历更多节点）。
影响：线程负载不均衡，无法充分利用多核性能。*/

/*不足 2：未处理线程安全问题
代码现状：并行查询中多个线程同时访问 KD 树的只读数据（如节点坐标、分割值），虽无写冲突，但未明确使用const修饰共享指针。
影响：可能导致代码可读性下降，潜在逻辑错误风险。*/

// 并行查询（保持不变）
vector<int> findNearestFlightLineParallel(const shared_ptr<KDNode> &root,
                                          const vector<QueryPoint> &queryPoints)
{
    // 保持原代码逻辑不变
    vector<int> results(queryPoints.size(), -1);
    if (!root)
        return results;

    auto worker = [&](size_t start, size_t end)
    {
        for (size_t i = start; i < end; ++i)
        {
            double minDist = numeric_limits<double>::max();
            int nearest = -1;
            searchKDTree(root, queryPoints[i], minDist, nearest);
            results[i] = nearest;
        }
    };

    if (queryPoints.size() < 200)
    {
        worker(0, queryPoints.size());
    }
    else
    {
        size_t threads = thread::hardware_concurrency();
        size_t chunk = queryPoints.size() / threads;
        vector<thread> ts;
        for (size_t i = 0; i < threads; ++i)
        {
            ts.emplace_back(worker, i * chunk, (i + 1) * chunk);
        }
        for (auto &t : ts)
            t.join();
    }
    return results;
}

int main()
{
    int numTestCases;
    cout << "请输入测试用例的数量: ";
    cin >> numTestCases;

    for (int t = 1; t <= numTestCases; ++t)
    {
        cout << "\n=== 测试用例 " << t << " ===" << endl;

        int numFlightLines;
        cout << "请输入飞行线的数量: ";
        cin >> numFlightLines;

        vector<FlightLine> flightLines(numFlightLines);
        int nextFlightLineId = 1; // 重置ID计数器

        for (int i = 0; i < numFlightLines; ++i)
        {
            cout << "请输入飞行线 " << i + 1 << " 的两个端点坐标 (x1 y1 x2 y2): ";
            cin >> flightLines[i].x1 >> flightLines[i].y1 >> flightLines[i].x2 >> flightLines[i].y2;
            flightLines[i].id = nextFlightLineId++;
        }

        auto root = buildKDTreeParallel(flightLines);

        int numQueryPoints;
        cout << "请输入查询点的数量: ";
        cin >> numQueryPoints;

        vector<QueryPoint> queryPoints(numQueryPoints);
        for (int i = 0; i < numQueryPoints; ++i)
        {
            cout << "请输入查询点 " << i + 1 << " 的坐标 (x y): ";
            cin >> queryPoints[i].x >> queryPoints[i].y;
        }

        vector<int> results = findNearestFlightLineParallel(root, queryPoints);

        cout << "\n测试用例 " << t << " 的结果:" << endl;
        for (size_t i = 0; i < results.size(); ++i)
        {
            cout << "查询点 " << i + 1 << " 的最近飞行线ID是: " << results[i] << endl;
        }

        char choice;
        do
        {
            cout << "\n是否要动态更新飞行线？(y/n): ";
            cin >> choice;

            if (choice == 'y')
            {
                cout << "请选择操作: 1-添加飞行线, 2-删除飞行线: ";
                int op;
                cin >> op;

                if (op == 1)
                {
                    FlightLine newLine;
                    cout << "请输入新飞行线的两个端点坐标 (x1 y1 x2 y2): ";
                    cin >> newLine.x1 >> newLine.y1 >> newLine.x2 >> newLine.y2;
                    newLine.id = nextFlightLineId++;

                    if (root)
                        root->insert(newLine); // 调用插入方法
                    else
                        root = make_shared<KDNode>(newLine, 0, (newLine.x1 + newLine.x2) / 2);

                    cout << "已添加新飞行线，ID为: " << newLine.id << endl;
                }
                else if (op == 2)
                {
                    int lineId;
                    cout << "请输入要删除的飞行线ID: ";
                    cin >> lineId;

                    if (root && root->remove(lineId))
                    { // 调用删除方法
                        cout << "已成功删除ID为 " << lineId << " 的飞行线" << endl;
                        // 清理空树
                        if (!root->left && !root->right)
                            root = nullptr;
                    }
                    else
                    {
                        cout << "未找到ID为 " << lineId << " 的飞行线！" << endl;
                    }
                }

                // 重新查询
                results = findNearestFlightLineParallel(root, queryPoints);
                cout << "\n更新后的查询结果:" << endl;
                for (size_t i = 0; i < results.size(); ++i)
                {
                    cout << "查询点 " << i + 1 << " 的最近飞行线ID是: " << results[i] << endl;
                }
            }
        } while (choice == 'y');
    }

    cout << "\n程序执行完毕，按Enter键退出...";
    cin.ignore(numeric_limits<streamsize>::max(), '\n');
    cin.get();
    return 0;
}